Section: New Results

Ressource allocation in vehicle sharing systems

Participants : Christine Fricker, Yousra Chabchoub.

Vehicle sharing systems are becoming an urban mode of transportation, and launched in many cities, as Velib' and Autolib' in Paris. Managing such systems is quite difficult. One of the major issues is the availability of the resources: vehicles or free slots to return them. These systems became a hot topic in Operation Research and the importance of stochasticity on the system behavior leads us to propose mathematical stochastic models. The problem is to understand the system behavior and how to manage these systems in order to improve the allocation of both resources to users. This work is in collaboration with El Sibai Rayane (ISEP), Plinio Santini Dester (École Polytechnique), Hanène Mohamed (Université Paris-Ouest), and Danielle Tibi (Université Paris Diderot).

Stochastic modelling of bike-sharing systems

The goal is to derive the stationary behavior of the state process in a quite general model: number of bikes in the stations and in routes between two stations. Our stochastic model is the first one taking into account the finite number of spots at the stations. The basic model for bike-sharing systems comes within the framework of closed networks with two types of nodes: single server/finite capacity nodes and infinite servers/infinite capacity nodes. The effect of local saturation is modeled by generalized blocking and rerouting procedures, under which, as a key argument, the stationary state is proved to have product-form. For a class of large closed Jackson networks submitted to capacity constraints, asymptotic independence of the nodes in normal traffic phase is proved at stationarity under mild assumptions, using a Local Limit Theorem. The limiting distributions of the queues are explicit. In the Statistical Mechanics terminology, the equivalence of ensembles - canonical and grand canonical - is proved for specific marginals. This widely extends the existing results on heterogeneous bike-sharing systems. The grand canonical approximation can then be used for adjusting the total number of bikes and the capacities of the stations to the expected demand. [12]

Local load balancing policies.

Recently we investigated some load balancing algorithms for stochastic networks to improve the bike sharing system behavior. We focus on the choice of the least loaded station among two to return the bike, the so called Power of choice. Nevertheless, in real systems, this choice is local. Thus the main challenge is to deal with the choice between two neighboring stations.

For that, a set of $N$ queues, with a local choice policy, is studied. When a customer arrives at queue $i$, he joins the least loaded queue between queues $i$ and $i+1$. When the load tends to zero, we obtain an asymptotic for the stationary distribution of the number of customers at a queue. The main result is that, in equilibrium, queue lengths decay geometrically when $\rho$ tends to 0, $N$ fixed. It allows to compare local choice, no choice and Power of choice. The local policy changes the exponential decay with respect to no choice but does not lead to an improvement (double exponential tail decay) comparable to the random choice model. [19].

For a bike-sharing homogeneous model, we study a deterministic cooperation between the stations, two by two. Analytic results are achieved in an homogeneous bike-sharing model. They concern the mean-field limit as the system is large, and its equilibrium point. Results on performance mainly involve an original closed form expression of the stationary blocking probability and new tight bounds for the mean of the total number of customers in the classical join-the-shortest-queue model. These results are compared by simulations with the policy where the users choose the least loaded between two neighboring stations. It turns out that, because of randomness, the choice between two neighbours gives better performance than grouping stations two by two.

It relies on new results for the classical system of two queues under the join-the-shortest-queue policy. We revisited the study of the stationary distribution. A simple analytical solution is proposed. Using standard generating function arguments, a simple expression of the blocking probability is derived, which as far as we know is original. Furthermore, from the balance equations, all stationary probabilities are obtained as explicit combinations of those of states $(0,k)$ for $0\le k\le K$. The blocking probability is also obtained for a variant with two queues under JSQ, where the constraint is on the total capacity of the system.

This extends to the infinite capacity and asymmetric cases, i.e., when the queues have different service rates. For the initial symmetric finite capacity model, the stationary probabilities of states $(0,k)$ can be obtained recursively from the blocking probability. In the other cases, they are implicitly determined through some functional equation that characterizes their generating function. For the infinite capacity symmetric model, we provide an elementary proof of a result by Cohen which gives the solution of the functional equation in terms of an infinite product with explicit zeroes and poles. See [9].

We use data, trip data (trips collected in a month) obtained from JCDecaux and reports on station status collected as open data, to test local choice policy. Indeed we designed and tested a new method that globally improves the distribution of the resources (bikes and docks) among the stations. It relies on a local small change in user behaviors, by adapting their trips to resource availability around their departure and arrival stations. Results show that, even with a partial user collaboration, the proposed method increases significantly the global balance of the bike sharing system and therefore the user satisfaction. This is done using trip data sets. The key of our study is to detect spatial outliers, objects having a behavior significantly different from their spatial neighbors, in a context where neighbors are heavily correlated. Moran scatterplot is a well-known method that exploits similarity between neighbors in order to detect spatial outliers. We proposed an improved version of Moran scatterplot, using a robust distance metric called Gower similarity. Using this new version of Moran scatterplot, we identified many spatial outliers stations (often with much more available bikes, or with much more empty docks during the day) in Velib. For the occupancy data set obtained by modifiying trips, the number of spatial outliers drastically decreases. See [18].